<?php
/**
 * User: helloJiu
 * Date: 2021/10/11
 * Time: 16:21
 */

namespace App\Algorithm\DP;


class EditDistance
{
    /**
     * 动态规划解决编辑距离问题
     * https://leetcode-cn.com/problems/edit-distance/
     * @param String $word1
     * @param String $word2
     * @return Integer
     */
    function minDistance($word1, $word2) {
        $dp = [];
        $len1 = strlen($word1);
        $len2 = strlen($word2);

        for($i = 0; $i<=$len1; $i++){
            $dp[$i][0] = $i;
        }

        for($j = 0; $j<=$len2; $j++){
            $dp[0][$j] = $j;
        }
        // $dp[$i][$j] 表示$word1[0:$i]和$word2[0:$j] 变更成相同所需的最少步骤

        for($i = 1; $i<=$len1; $i++){
            for($j = 1; $j<=$len2; $j++){
                if($word1[$i-1] == $word2[$j-1]){
                    $dp[$i][$j] = $dp[$i-1][$j-1];
                }else{
                    $dp[$i][$j] = min($dp[$i-1][$j], $dp[$i][$j-1], $dp[$i-1][$j-1]) + 1;
                }
            }
        }

        return $dp[$len1][$len2];
    }
}